#include "stdafx.h"
#include "graph.h"

using namespace std;


int * CGraph::Dijkstra( int u ) {

	int * d = new int[ cV ];
	vector< int > conseqs;
	struct edge v;
	struct edge tmpPath;
	int weight;
 

	edges.clear();

	for( int i=0; i<cV; ++i ) {

		// uzupelnianie tablicy najkrotszych sciezek
		// wartosciami niezdefiniowanymi
		d[ i ] = INT_MAX / 2;

		// wypelnianie kopca krawedziami
		tmpPath.vA = u;
		tmpPath.vB = i + 1;
		tmpPath.weight = d[ i ];
		edges.insert( tmpPath );
	}

	// z wierzcholka u do samego siebie
	// droga jest rowna 0
	d[ u - 1 ] = 0;

	int c_i;

	while( !edges.empty() ) { 

		// pobranie sciezki o najmniejszej wadze
		v = *( edges.begin() );
		// usuniecie sciezki o najmniejszej wadze
		edges.erase( edges.begin() );

		// wyszukanie nastepnikow wierzcholka B
		// do ktorego prowadzi najkrotsza sciezka
		conseqs = GetConsequents( v.vB );
		
		for (int i=0; i<conseqs.size(); ++i ) {
		
			c_i = conseqs[i];
			weight = GetWeight( v.vB, c_i );
			// sprawdzenie czy sciezka przez wierzcholek B
			// jest krotsza niz sciezka przez jeden z jego nastepnikow
			if( d[ c_i - 1 ] > d[ v.vB - 1 ] + weight ) {

				// znalezienie bierzacego wierzcholka w drzewie
				tmpPath.vA = u;
				tmpPath.vB = c_i;
				tmpPath.weight = d[ c_i - 1 ];
				edges.erase( edges.find( tmpPath ) );
				// zaktualizowanie bierzacej tablicy najkrotszych sciezek
				d[ c_i - 1 ] = d[ v.vB - 1 ] + weight;
				tmpPath.weight = d[ c_i - 1 ];
				// zaktualizowanie drzewa
				edges.insert( tmpPath );
			}
		}
	}

	
	return d;
}